结合HSV与纹理特征的视频阴影消除算法

目的 在视频监控目标检测应用中,场景中的阴影会直接影响目标检测的准确度,因此阴影抑制算法研究显得尤为重要。目前广泛使用的是HSV（hue,saturation,value）阴影抑制方法,但是该方法存在由于亮度比值的阈值不稳定而造成将运动目标也检测为阴影的问题。针对该问题,本文提出了一种结合HSV与纹理特征的视频阴影消除方法。方法 首先将输入的图像使用传统的混合高斯模型建立背景并在灰度空间中提取前景,其次在HSV空间使用亮度比的阈值方法检测阴影,二者综合得到运动目标;针对由于亮度比值的阈值不稳定而导致的前景误检为阴影的问题,采用了LBP（local binary pattern）算子结合大津阈值（OTSU）提取部分运动目标。最后将LBP算子结合大津阈值提取的部分运动目标与HSV空间检测的目标两者相或,最终去除运动目标的阴影。结果 本文选用在CVPR-ATON和CAVIAR标准视频库中多个场景的阴影视频,将本文算法与SNP算法、SP算法、DNM1算法和DNM2算法进行对比仿真,实验结果表明本文算法在阴影检测率和阴影识别率的平均值上提升约10%。结论 本文提出的视频阴影消除算法结合了HSV与纹理特征,可以在不同的环境中有效地去除阴影,运动目标保留完整,可适用于智能视频监控、遥感图像和人机交互中。     

求解最小闭包球问题改进的SMO-型算法

研究n维空间中m个点的最小闭包球(MEB)问题。通过结合确定并删除内部点的技术到序列最小最优化(SMO)方法中,提出一种近似求解MEB问题的改进的SMO-型算法。证明了该算法具有线性收敛性。数值结果表明对于一些mn的大规模数据集,改进的算法与原算法相比速度可以提高10倍以上。尤其,当n等于100且m等于100000时,改进的SMO-型算法仅需执行8s。此外,对于n等于10000且m等于1000的大规模数据集,改进的算法也仅需执行150s。     

Combining intensional with extensional query evaluation in tuple independent probabilistic databases

In this paper, we prove that a query plan is safe in tuple independent probabilistic databases if and only if its every answer tuple is tree structured in probabilistic graphical models. We classify hierarchical queries into core and non-core hierarchical queries and show that the existing methods can only generate safe plans for core hierarchical queries. Inspired by the bucket elimination framework, we give the sufficient and necessary conditions for the answer relation of every candidate sub-query to be used as a base relation. Finally, the proposed algorithm generates safe plans for extensional query evaluation on non-boolean hierarchical queries and invokes the SPROUT algorithm [24] for intensional query evaluation on boolean queries. A case study on the TPC-H benchmark reveals that the safe plans of Q7 and Q8 can be evaluated efficiently. Furthermore, extensive experiments show that safe plans generated by the proposed algorithm scale well.     

An approximate duplicate elimination in RFID data streams

The RFID technology has been applied to a wide range of areas since it does not require contact in detecting RFID tags. However, due to the multiple readings in many cases in detecting an RFID tag and the deployment of multiple readers, RFID data contains many duplicates. Since RFID data is generated in a streaming fashion, it is difficult to remove duplicates in one pass with limited memory. We propose one pass approximate methods based on Bloom Filters using a small amount of memory. We first devise Time Bloom Filters as a simple extension to Bloom Filters. We then propose Time Interval Bloom Filters to reduce errors. Time Interval Bloom Filters need more space than Time Bloom Filters. We propose a method to reduce space for Time Interval Bloom Filters. Since Time Bloom Filters and Time Interval Bloom Filters are based on Bloom Filters, they do not produce false negative errors. Experimental results show that our approaches can effectively remove duplicates in RFID data streams in one pass with a small amount of memory.     

Corrected upper bounds for free-cut elimination

Free-cut elimination allows cut elimination to be carried out in the presence of non-logical axioms. Formulas in a proof are anchored provided they originate in a non-logical axiom or non-logical inference. This paper corrects and strengthens earlier upper bounds on the size of free-cut elimination. The correction requires that the notion of a free cut be modified so that a cut formula is anchored provided that all of its introductions are anchored, instead of only requiring that one of its introductions is anchored. With the correction, the originally proved size upper bounds remain unchanged. These results also apply to partial cut elimination. We also apply these bounds to elimination of cuts in propositional logic.If the non-logical inferences are closed under cut and infer only atomic formulas, then all cuts can be eliminated. This extends earlier results of Takeuti and of Negri and von Plato.     

Image reconstruction from in-line Fresnel holograms by using coherent background elimination

Image reconstruction from in-line Fresnel holograms by eliminating a coherent background is studied by computer simulation. The coherent background is calculated by averaging an intensity of a recorded hologram. The quality of the reconstructed image is measured by using a ratio of peak signal to noise. In comparison with the conventional reconstruction method, the results show that the background elimination can improve significantly the quality of the reconstructed images. The text was submitted by the authors in English.     

Efficient Sequence Alignment with Side-Constraints by Cluster Tree Elimination

Aligning DNA and protein sequences is a core technique in molecular biology. Often, it is desirable to include partial prior knowledge and conditions in an alignment. Going beyond prior work, we aim at the integration of such side constraints in free combination into alignment algorithms. The most common and successful technique for efficient alignment algorithms is dynamic programming (DP). However, a weakness of DP is that one cannot include additional constraints without specifically tailoring a new DP algorithm. Here, we discuss a declarative approach that is based on constraint techniques and show how it can be extended by formulating additional knowledge as constraints. We take special care to obtain the efficiency of DP for sequence alignment. This is achieved by careful modeling and applying proper solving strategies. Finally, we apply our method to the scanning for RNA motifs in large sequences. This case study demonstrates how the new approach can be used in real biological problems. A prototypic implementation of the method is available at .     

Fraction-free matrix factors: new forms for LU and QR factors

Gaussian elimination and LU factoring have been greatly studied from the algorithmic point of view, but much less from the point view of the best output format. In this paper, we give new output formats for fraction free LU factoring and for QR factoring. The formats and the algorithms used to obtain them are valid for any matrix system in which the entries are taken from an integral domain, not just for integer matrix systems. After discussing the new output format of LU factoring, the complexity analysis for the fraction free algorithm and fraction free output is given. Our new output format contains smaller entries than previously suggested forms, and it avoids the gcd computations required by some other partially fraction free computations. As applications of our fraction free algorithm and format, we demonstrate how to construct a fraction free QR factorization and how to solve linear systems within a given domain.     

计算对称带状矩阵特征值问题的并行二分／多分法

文中提出了在分布式环境下并行求解对称带状矩阵特征值问题的并行二分．多分法及其改进,该算法利用变形高斯消去法计算对称带状矩阵的Sturm序列,并利用Rayleigh商迭代对二分／多分法加以改进,在算法的并行执行过程中,各处理机间不需通信,特别适用在分布式环境下的并行计算,最后给出了数值实验结果。